package alibaba;

import java.util.Scanner;

/**
 * 求最长不减子序列
 * ref:
 * http://blog.csdn.net/wy19910326/article/details/7229350
 * http://www.cnblogs.com/lonelycatcher/archive/2011/07/28/2119123.html
 */
public class Main {
    /**
     * 设f(i)表示L中以ai为末元素的最长递增子序列的长度。则有如下的递推方程：
     * 这个递推方程的意思是，在求以ai为末元素的最长递增子序列时，找到所有序号在L前面且小于ai的元素aj，即j<i且aj<ai。
     * 如果这样的元素存在，那么对所有aj,都有一个以aj为末元素的最长递增子序列的长度f(j)，把其中最大的f(j)选出来，
     * 那么f(i)就等于最大的f(j)加上1，即以ai为末元素的最长递增子序列，等于以使f(j)最大的那个aj为末元素的递增子序列最末再加上ai；
     * 如果这样的元素不存在，那么ai自身构成一个长度为1的以ai为末元素的递增子序列。
     * @param peaches
     * @return
     */
    private static int pick(int[] peaches) {
        int n = peaches.length;
        int[] dp = new int[n+1];
        dp[1] = 1;
        int ans = 0;
        for (int i = 2; i <= n; i++) {
            ans = dp[i];
            for (int j = 1; j < i; j++) {
                if (peaches[i - 1] >= peaches[j - 1] && dp[j] > ans) {
                    ans = dp[j];
                }
            }
            dp[i] = ans + 1;
        }
        ans = 0;
        // 取最大的返回
        for (int i = 0; i <=n; i++) {
            System.out.print(dp[i] + " ");
            if(dp[i] > ans) {
                ans = dp[i];
            }
        }
        return ans;
    }

    static  void lis1(float[] L)
    {
        int n = L.length;
        float[] B = new float[n+1];//数组B；
        B[0]=-10000;//把B[0]设为最小，假设任何输入都大于-10000；
        B[1]=L[0];//初始时，最大递增子序列长度为1的最末元素为a1
        int Len = 1;//Len为当前最大递增子序列长度，初始化为1；
        int p,r,m;//p,r,m分别为二分查找的上界，下界和中点；
        for(int i = 1;i<n;i++)
        {
            p=0;r=Len;
            while(p<=r)//二分查找最末元素小于ai+1的长度最大的最大递增子序列；
            {
                m = (p+r)/2;
                if(B[m]<L[i]) p = m+1;
                else r = m-1;
            }
            B[p] = L[i];//将长度为p的最大递增子序列的当前最末元素置为ai+1;
            if(p>Len) Len++;//更新当前最大递增子序列长度；


        }
        System.out.println(Len);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int trees = sc.nextInt();
            int[] peaches = new int[trees];
            for (int i = 0; i < trees; i++) {
                peaches[i] = sc.nextInt();
            }
            System.out.println(pick(peaches));
        }
    }
}
